package com.dxb.test.sort;

/**
 * 归并排序
 * 基本思想：
 * 将数组分成2组A，B，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了？
 * 可以将A，B组各自再分成2组。依次类推，当分出来的小组只有1个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了。
 * 这样通过先递归的分解数列，再合并数列就完成了归并排序。
 */
public class MergeSort extends BaseSort {
    public MergeSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        internalMergeSort(new int[length], 0, length - 1);
    }

    private void internalMergeSort(int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        int middle = (right + left) / 2;
        internalMergeSort(temp, left, middle);
        internalMergeSort(temp, middle + 1, right);
        mergeSortedArray(temp, left, middle, right);
    }

    private void mergeSortedArray(int[] temp, int left, int middle, int right) {
        int i = left;
        int j = middle + 1;
        int k = 0;
        while (i <= middle && j <= right) {
            temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }
        while (i <= middle) {
            temp[k++] = array[i++];
        }
        while (j <= right) {
            temp[k++] = array[j++];
        }
        //把数据复制回原数组
        for (int l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        MergeSort qs = new MergeSort(array);
        qs.run();
    }
}
